package Leetcode第一期;

import java.util.LinkedList;

/**
 * @author : K k
 * @date : 11:02 2020/5/15
 */
public class 插入区间_57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int newStart = newInterval[0], newEnd = newInterval[1];
        int idx = 0, n = intervals.length;
        LinkedList<int[]> output = new LinkedList<int[]>();

        //先将前面区间放入列表
        while (idx<n&&intervals[idx][0]<newStart){
            output.add(intervals[idx++]);
        }

        //将列表中的最后一个数组与新插入数组比较
        int[] interval=new int[2];
        if (output.isEmpty()||output.getLast()[1]<newStart){
            output.add(newInterval);
        }else {
            interval=output.removeLast();
            interval[1]=Math.max(interval[1],newEnd);
            output.add(interval);
        }

        while (idx<n){
            interval=intervals[idx++];
            int start=interval[0];int end=interval[1];
            if (output.getLast()[1]<start){
                output.add(interval );
            }else {
                interval=output.removeLast();
                interval[1]=Math.max(interval[1],end);
                output.add(interval);
            }
        }
        return output.toArray(new int[output.size()][2]);

    }
}
